package com.hy.stack.monotoneStack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NextLargestElement {

    /**
     * 496.下一个更大元素 I
     * 力扣题目链接
     *
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
     *
     * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
     *
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
     *
     * 示例 1:
     *
     * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
     * 输出: [-1,3,-1]
     * 解释:
     * 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
     * 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
     * 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
     *
     * 示例 2:
     * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
     * 输出: [3,-1]
     * 解释:
     * 对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
     * 对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出-1 。
     *
     *  思路
     * 做本题之前，建议先做一下739. 每日温度
     *
     * 在739. 每日温度中是求每个元素下一个比当前元素大的元素的位置。
     *
     * 本题则是说nums1 是 nums2的子集，找nums1中的元素在nums2中下一个比当前元素大的元素。
     *
     * 看上去和739. 每日温度 就如出一辙了。
     *
     * 几乎是一样的，但是这么绕了一下，其实还上升了一点难度。
     *
     * 需要对单调栈使用的更熟练一些，才能顺利的把本题写出来。
     *
     * 从题目示例中我们可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素，那么就要定义一个和nums1一样大小的数组result来存放结果。
     *
     * 这么定义这个result数组初始化应该为多少呢？
     *
     * 题目说如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。
     *
     * 在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
     *
     * 注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
     *
     * 没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
     *
     * 使用单调栈，首先要想单调栈是从大到小还是从小到大。
     *
     * 本题和739. 每日温度是一样的。
     *
     * 栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。
     *
     * 可能这里有一些同学不理解，那么可以自己尝试一下用递减栈，能不能求出来。其实递减栈就是求右边第一个比自己小的元素了。
     *
     * 接下来就要分析如下三种情况，一定要分析清楚。
     *
     * 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
     * 此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
     *
     * 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
     * 如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
     *
     * 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
     * 此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
     *
     * 判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。
     *
     * 记录结果这块逻辑有一点小绕，要清楚，此时栈顶元素在nums2中右面第一个大的元素是nums2[i]即当前遍历元素。
     *
     *
     * @param num1
     * @param num2
     * @return
     */
    public static int [] nextLargestElement(int [] num1,int [] num2){
        Stack<Integer> st = new Stack<>();
        int [] res = new int[num1.length];
        // 填充数据
        Arrays.fill(res,-1);
        Map<Integer,Integer> map =  new HashMap<>();
        for (int i = 0; i < num1.length; i++) {
            map.put(num1[i],i);
        }
        st.push(0);

        for (int i = 1; i < num2.length; i++) {
            if (num2[i] <= num2[st.peek()]){
                st.add(i);
            }else {
                while (!st.isEmpty() && num2[i] > num2[st.peek()]){
                    if (map.containsKey(num2[st.peek()])){
                        Integer index = map.get(num2[st.peek()]);
                        res[index] = num2[i];
                    }
                    st.pop();
                }
                st.add(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int [] nums1 = {4,1,2},nums2 = {1,3,4,2};

        System.out.println("res: "+ Arrays.toString(nextLargestElement(nums1,nums2)));
    }
}
